﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Trie
{
    public class Trie
    {
        public TrieNode rootNode = null;

        public Trie ()
	    {
            rootNode = new TrieNode
            {
                Data  = 0,
                Parent = null,
                Word = string.Empty,
                Childs = new Dictionary<int, TrieNode>()
            };
            BuildTrie();
	    }

        private void BuildTrie()
        {
            string allData = null;
            using (StreamReader reader = new StreamReader(new FileStream(@"D:\dict.txt", FileMode.Open)))
            {
                allData = reader.ReadToEnd();
            }
            TrieNode node = rootNode;
            foreach (var item in allData)
            {
                if (item == '\r' || item == '\n' || item ==' ' || item == '.' || item == ',' || item == ':' || item ==';' || item =='-')
                {
                    node = rootNode;
                }
                else
                {
                    node = AddNode(node, item);
                }
            }
        }
        public TrieNode AddNode(TrieNode node, int num)
        {
            TrieNode n;
            if (node.Childs.TryGetValue(num, out n))
                return n;

            var newNode = new TrieNode()
            {
                Data = num,
                Parent = node,
                Word = string.Concat(node.Word, (char)num),
                Childs = new Dictionary<int, TrieNode>()
            };
            node.Childs.Add(num, newNode);
            return newNode;
        }

        TrieNode node = null;
        public List<TrieNode> Search(char[] nums)
        {
            resultNodes.Clear();
            node = null;
            if (node == null)
                node = rootNode;
            foreach (var item in nums)
            {
                resultNodes.Clear();
                node = Search2(node, item);
            }            
            return resultNodes;
        }

        List<TrieNode> resultNodes = new List<TrieNode>();

        public TrieNode Search2(TrieNode node, int num)
        {
            if (node == null) return node;


            TrieNode n;
            if (node.Childs.TryGetValue(num, out n))
            {
                foreach (var item in n.Childs)
                {
                    Search2(n, item.Value.Data);
                }
                if (n.Childs.Count == 0)
                    resultNodes.Add(n);
            }            
            return n;
        }
    }

    public class TrieNode
    {
        public int Data {get; set;}
        public TrieNode Parent {get; set;}

        public Dictionary<int, TrieNode> Childs { get; set; }

        public string Word {get; set;}
    }
}
